package alo;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @ClassName lru
 * @Description TODO
 * @Author Fanxc
 * @DATE 2021/4/15 20:34
 * @Version 1.0
 */


public class lru2 {
    private Map<Integer, Node> map = new HashMap<>();
    private DoubleList list=new DoubleList();
    private int k;
    public int[] LRU (int[][] operators, int k) {
        this.k = k;
        int len = (int)Arrays.stream(operators).filter(x -> x[0] == 2).count();
        int[] res = new int[len];
        for(int i = 0, j = 0; i < operators.length; i++) {
            if(operators[i][0] == 1) {
                set(operators[i][1], operators[i][2]);
            } else {
                res[j++] = get(operators[i][1]);
            }
        }
        return res;
    }

    private void set(int key, int val) {
        Node node= new Node(key, val);
        if(get(key) > -1) {//如果有了，进行值更新
            list.remove(node);
            list.addFirst(node);
            map.put(key,node);
        } else {
            if(map.size() == k) {//如果满了
                int rk = list.tail.prev.key;
                list.removeLast();
                map.remove(rk);
            }
            list.addFirst(node);
            map.put(key, node);
        }

    }

    private int get(int key) {
        if(map.containsKey(key)) {
            Node node = map.get(key);
            list.remove(node);
            list.addFirst(node);
            return node.val;
        }
        return -1;
    }



    static class Node{
        int key, val;
        Node prev, next;
        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    class DoubleList{

        private Node head;
        private Node tail;
        private int size=0;
        public DoubleList(){
            head = new Node(-1,-1);
            tail = new Node(-1,-1);
            head.next = tail;
            tail.prev = head;
        }
        public void addFirst(Node node){
            node.next=head.next;
            head.next.prev = node;
            head.next = node;
            node.prev = head;
            size++;
        }

        public void remove(Node node){
            node.prev.next=node.next;
            node.next.prev=node.prev;
            size--;
        }

        public Node removeLast(){
            Node node=tail.prev;
            tail.prev.prev.next = tail;
            tail.prev = tail.prev.prev;
            size--;
            return node;
        }
        // 返回链表⻓度，时间 O(1)
        public int size(){
            return size;
        }
    }
}

